#include "sort.h"

/*  希尔排序    */
// 1.预排序
// 2.直接插入排序
void ShellSort(int *a, int n)
{
    int gap = n / 2;
    while (gap >= 1)
    {
        //--------------------完成以gap为间距的插入排序----------------------------//
        int i = 0;
        for (i = 0; i < n - gap; i++)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
        //--------------------完成以gap为间距的插入排序----------------------------//

        gap /= 2; // 更新gap，进行下一次预排序。当 gap == 1 时则变为直接插入排序。
        // gap = gap / 3 + 1; 也行，比 gap /= 2; 多预排序几次。
        // gap = gap / 3 ; 不行！无法保证 gap == 1

        // 测试
        // 每次预排序完成时打印一下，看看效果。
        printArr(a, n);
        // 可以看到，gap越大时，大的数越快速地跳到最后，gap越小时，越能使数组有序。
    }
}

// 希尔排序 —— 升序
void ShellSort_2(int *a, int n)
{
    int gap = n;
    while (gap > 1) //和上面的区别在这。
    {
        // 更新gap
        gap = gap / 3 + 1;

        //-----------------以gap为间隔完成1次预排序--------------------//
        int i = 0;
        for (i = 0; i < n - gap; i++)
        {
            int end = i; // 第一次，end 为 0; 第二次，end为 1；...；最后一次end为 n-gap-1
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                    break;
            }
            a[end + gap] = tmp;
        }
        //-----------------以gap为间隔完成1次预排序--------------------//
    }
}